package 剑指offer;

import util.LogUtils;

import com.sun.swing.internal.plaf.basic.resources.basic;


/**
 * 回溯法：矩陣中的路徑
 * 
 * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
 * 思路：
 * 	
	    首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。
	    重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。
	    由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。
	    由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。
	
	    当矩阵中坐标为（row,col）的格子和路径字
 * 
 * 參考思路：http://blog.csdn.net/huzhigenlaohu/article/details/51867219
 * @Date 2017-11-11 12：32
 * @author zouchao
 *
 */
public class _012_Solution {
	
	private static final String TAG = "回溯法：矩陣中的路徑";
	private int N, n;
	private int[] mMatrix;
	private int mRowCount, mColCount;
	private boolean[] mFlag;
	public boolean solution(int[] matrix, int rowCount, int colCount, int[] substr) {
		mMatrix = matrix;
		N = matrix.length;
		n = substr.length;
		mFlag = new boolean[N];
		mRowCount = rowCount;
		mColCount = colCount;
		for (int row = 0; row < rowCount; row ++) 
			for (int col = 0; col < colCount; col ++) 
//				if (helper(mMatrix, mRowCount, mColCount, row, col, substr, 0, mFlag))	return true;
				if (helper(row, col,  0, substr))	return true;
		return false;
	} 
	
	/**
	 * @param row
	 * @param col
	 * @param offset
	 * @param substr
	 * @param rs
	 * @return
	 */
	private boolean helper(int row, int col, int offset, int[] substr) {
		if (row>=mRowCount || col>=mColCount
				|| row<0 || col<0)	
			return false;
		int index = row*mColCount+col;	
//		if (offset>=N || offset>=n || index>=N || index>=n)	
//			return false;
		if (mMatrix[index] != substr[offset])	
			return false;
		if (mFlag[index])	
			return false;	
		if (offset >= n-1)	return true;
		mFlag[index] = true;
		if (helper(row+1, col, offset+1, substr) || helper(row, col+1, offset+1, substr)
				|| helper(row-1, col, offset+1, substr) || helper(row, col-1, offset+1, substr))
			return true;
		mFlag[index] = false;
		return false;
	}
	
	/**
	 * 标准代码
	 * @param matrix
	 * @param rows
	 * @param cols
	 * @param i
	 * @param j
	 * @param str
	 * @param k
	 * @param flag
	 * @return
	 */
    private boolean helper(int[] matrix, int rows, int cols, int i, int j, int[] str, int k, boolean[] flag) {
        int index = i * cols + j;
        if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index])
            return false;
        if(k == str.length - 1) return true;
        flag[index] = true;
        if (helper(matrix, rows, cols, i - 1, j, str, k + 1, flag)
                || helper(matrix, rows, cols, i + 1, j, str, k + 1, flag)
                || helper(matrix, rows, cols, i, j - 1, str, k + 1, flag)
                || helper(matrix, rows, cols, i, j + 1, str, k + 1, flag)) {
            return true;
        }
        flag[index] = false;
        return false;
    }
	
	public static void main(String[] args) {
		LogUtils.println(TAG, new _012_Solution().solution(
				new int[] {'a', 'b', 'c', 'e', 's', 'f', 'c', 's', 'a', 'd', 'e', 'e'}, 
				3, 4, 
				new int[] {'b', 'c', 'c', 'e', 'd'})
		);
	}
}
